package com.LeetCode.dp.KaterLan;

import org.junit.Test;

/**
 * n 个人围成一圈，总共握手 n / 2 次，求总共有多少总方案
 */
public class DisjointedHandshake {


    public int numberOfWays(int num_people) {
        long mod = 1000000007L;
        int[] dp = new int[num_people / 2 + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i<= num_people/2; i++){
            for(int j = 0; j< i; j++){
                dp[i] += (dp[j] * dp[i - j - 1])%mod;
            }
        }
        return dp[num_people / 2];
    }

    @Test
    public void test(){
        System.out.println(numberOfWays(8));
    }
}
